#include <iostream>
#include <vector>
using namespace std;
bool findTarget(vector<vector<int>>& nums, int target) {
	int i = nums.size() - 1;
	int j = 0;
	while (i >= 0 && j < nums[0].size()) {
		if (target < nums[i][j]) {
			--i;
		}
		else if (target > nums[i][j]) {
			++j;
		}
		else return true;
	}
	return false;
}

void Test(char* name, vector<vector<int>>& nums, int target,bool answer) {
	if (name != nullptr) {
		cout << name << endl;
	}
	bool result = findTarget(nums,target);
	if (answer == result) {
		cout << "passed" << endl;
	}
	else cout << "failed" << endl;
}

void test1() {
	vector<vector<int>> nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	Test((char*)"Test1", nums, 7, true);
}

void test2() {
	vector<vector<int>> nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	Test((char*)"Test2", nums, 5, false);
}

void test3() {
	vector<vector<int>> nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	Test((char*)"Test3", nums, 1, true);
}

void test4() {
	vector<vector<int>> nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	Test((char*)"Test4", nums, 15, true);
}

void test5() {
	vector<vector<int>> nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	Test((char*)"Test5", nums, 0, false);
}

void test6() {
	vector<vector<int>> nums = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	Test((char*)"Test6", nums, 16, false);
}
void test7() {
	vector<vector<int>> nums;
	Test((char*)"Test7", nums, 0, false);
}
int main() {
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	test7();
	return 0;
}